1. Field of the Invention
The invention relates to data processing systems, and more particularly to the scheduling and dispatching of processes in multiprocessing systems.
2. Description of the Prior Art
A multiprocessing system is able to execute simultaneously two or more computer programs or sequences of instructions. In a tightly-coupled multiprocessing system several processors may be connected to a single, shared memory. These systems multiplex numerous concurrent functions or tasks on one or more of the processors. Facilities must be provided for assigning available processors to tasks which are ready to be executed. Prior approaches have included software, firmware, and hardware types of systems.
Of the prior software techniques, there are the master-slave types of systems wherein one processor performs executive functions to allocate tasks to the other processors in the system (Mellen et al. U.S. Pat. No. 3,530,438 and Barbour U.S. Pat. No. 3,984,817).
There are also systems that utilize identical processors wherein none of them take on the role of the master. These systems utilize a central control wherein the software for task assignment is stored in memory (Driscoll U.S. Pat. No. 3,496,551 and Ochsner U.S. Pat. No. 3,348,210). Finally there are those systems wherein a special instruction is provided for implementing task assignment in each processor (Podvin U.S. Pat. No. 3,614,745 and Clark U.S. Pat. No. 3,725,864).
Techniques utilizing firmware use special-purpose microprogrammed controllers to perform the scheduling and dispatching functions. (Nadir U.S. Pat. No. 4,011,545, Valassis et al. U.S. Pat. No. 3,959,775, Tucker U.S. Pat. No. 3,449,722, Anceau et al. U.S. Pat. No. 4,015,242 and Brown U.S. Pat. No. 3,896,418).
None of the prior art data processing systems take full advantage of recent advances in the state-of-the-art of very large-scale, integrated circuit technology. Accordingly, the performance of these prior systems is low and programming to support multiprocessing is very complex.
With respect to the prior software techniques, while they are capable of performing complex multiprocessing operations, they suffer from the high costs of control programming to support these operations. The firmware techniques, while reducing somewhat the programming costs of the software techniques, lack flexibility, and lack general-purpose application.
The hardware techniques of the prior art also lack flexibility because they are able to handle only synchronous types of operations. They also lack the necessary hardware mechanisms to effectively communicate between various asynchronous operations without resort to costly control-program support for such operations, for example, interrupts at the processor level.
It is therefore a primary object of the present invention to provide a process scheduling and dispatching apparatus which is fast and economical, and which is designed to efficiently utilize very large-scale, integrated circuit technology.
It is also an object of this invention to provide a hardware mechanism for the isolation of and communication between tasks multiplexed to run concurrently on one or more processors, and to provide for facilities to automatically assign available processors to ready-to-run tasks.